const int N = 1005, M = 40005;
typedef int Type;
const Type INF = 0x3f3f3f3f;

struct Edge {
	int u, v;
	Type dist;
	Edge() {}
	Edge(int u, int v, Type d) : u(u), v(v), dist(d) {}
};

struct Directed_MST {
	Edge e[M];
	int n, m, vis[N], pre[N], id[N];
	Type in[N];

	void init(int n) {this->n = n;m = 0;}
	void add_Edge(int u, int v, Type dist) {e[m++] = Edge(u, v, dist);}
	Type dir_mst(int root) {
		Type ans = 0;
		while (true) {
			for (int i = 0; i < n; i++) in[i] = INF;
			for (int i = 0; i < m; i++) { //find min edge
				int u = e[i].u, v = e[i].v;
				if (e[i].dist < in[v] && u != v) {
					in[v] = e[i].dist; pre[v] = u;
				}}
			for (int i = 0; i < n; i++) { //judge
				if (i == root) continue;
				if (in[i] == INF) return -1;
			}
			int cnt = 0; in[root] = 0;
			memset(id, -1, sizeof(id));
			memset(vis, -1, sizeof(vis));
			for (int i = 0; i < n; i++) { //find circle
				ans += in[i]; int v = i;
				while (vis[v] != i && id[v] == -1 && v != root) {
					vis[v] = i; v = pre[v];
				}
				if (v != root && id[v] == -1) {
					for (int u = pre[v]; u != v; u = pre[u])
						id[u] = cnt;
					id[v] = cnt++;
				}
			}
			if (cnt == 0) break;
			for (int i = 0; i < n; i++)
				if (id[i] == -1) id[i] = cnt++;
			for (int i = 0; i < m; i++) {
				int v = e[i].v;
				e[i].u = id[e[i].u];
				e[i].v = id[e[i].v];
				if (e[i].u != e[i].v)
					e[i].dist -= in[v];
			}
			n = cnt; root = id[root];
		}
		return ans;
	}
} gao;
